import re
import math
import operator as op

def pi():
	'''Return the approximate value of pi.'''

	return math.pi

def e():
	'''Return the approximate value of e.'''

	return math.e

def root(base, exp):
	'''Return the *exp* root of *base*.'''

	return base ** (1.0/exp)


class RPN(object):
	'''Reverse Polish Notation interpreter.

	This object is able to evaluate RPN expressions
	such as::

		5 5 +
		1 neg 2 + abs 7 **
		5 radians sin 7 +
		4 pi + sqrt
		2 3 root

	The input tokens can be integers of floats, while the
	operators can be defined by the user at instantiation time.

	This can be accomplished passing an *operators* argument
	to the costructor.
	It should be a dictionary whose keys are the operator strings
	and whose values are 2-element tuples of the form::

		(function, number of operands)

	The tokens are obtained with a simple str.split method call,
	bute this can be easily changed in subclassing rewriting the
	tokenize method.

	If no *operators* argument is supplied than the default is
	used.
	The operators avaiable by default are::

		binary operators:

		+	   sum
		-	   subtraction
		*	   multiplication
		/	   division
		**	  esponentiation
		%	   reminder
		root	root (2 3 root -> third root of 2)
		log	 logarithm
		
		unary operators:
		
		abs	 absolute value
		neg	 change sign to the value
		sqrt	square root
		sin	 sine expressed in radians
		cos	 cosine expressed in radians
		tan	 tangent expressed in radians
		radians transforms degrees in radians
		ln	  natural logarithm
		log10   logarithm in base 10
		
		ternary operators:
		
		^	   base**exponent % module
		
		Constants(operators without operands):
		
		pi	  Approximation of pi
		e	   Approximation of e
		'''

	def __init__(self, operators=None):

		if operators is None:
			self._operators = {
				'+'   : (op.add, 2),
				'-'   : (op.sub, 2),
				'*'   : (op.mul, 2),
				'^'   : (pow,	3),
				'**'  : (pow,	2,),
				'/'   : (op.div, 2),
				'%'   : (op.mod, 2),
				'neg' : (op.neg, 1),
				'abs' : (abs,	1),
				'pi'  : (pi,	 0),
				'e'   : (e,	  0),
				'sqrt': (math.sqrt,1),
				'root': (root, 2),
				'sin' : (math.sin, 1),
				'radians':(math.radians, 1),
				'cos' : (math.cos, 1),
				'tan' : (math.tan, 1),
				'ln'  : (math.log, 1),
				'log' : (math.log, 2),
				'log10':(math.log10,1),
				}
		else:
			self._operators = dict(operators)
		
		self._token_types = [
			(self.is_input_token, self.handle_input_token),
			(self.is_operator_token, self.handle_operator_token)
			]

	def tokenize(self, string):
		'''Return a sequence of token from the given string.'''

		return [tok for tok in string.split() if tok]

	def evaluate(self, operator, operands):
	   '''Evaluates the expression composed of the given
	   operator and operands.
	   '''
	   return self._operators[operator][0](*operands)

	def evaluate_input(self, token):
		'''Evaluates an input token.'''
		
		try:
			return int(token)
		except ValueError:
			return float(token)

	def is_input_token(self, tok):
		'''Return True if *tok* can be considered an input token.'''
		number_rgx_text = (r'(?P<exp>\d+(\.\d+)?[eE][+-]?\d+(\.\d+)?)|'
						   r'(?P<float>(\d+\.\d*)|(\d*\.\d+))|'
						   r'(?P<int>\d+)')
		number_rgx = re.compile(number_rgx_text)
		return bool(number_rgx.match(tok))

	def is_operator_token(self, tok):
		'''Return True if *tok* can be considered an input token.'''

		return tok in self._operators
	
	def handle_input_token(self, tok, stack):
		'''Handles an input token.'''
		
		stack.append(self.evaluate_input(tok))
	
	def handle_operator_token(self, tok, stack):
		'''Handles an operatork token.'''
		
		number_of_operands = self._operators[tok][1]
		if len(stack) < number_of_operands:
			raise SyntaxError('Too few arguments for %r operator.' % tok)
		operands = stack[:number_of_operands]
		del stack[:number_of_operands]
		stack.insert(0, self.evaluate(tok, operands))
	
	def execute(self, code):
		'''Executes an RPN code returning the result.'''
		
		stack = []
		for tok in self.tokenize(code):
			for is_tok_type, handle_tok_type in self._token_types:
				if is_tok_type(tok):
					handle_tok_type(tok, stack)
					break
			else:
				raise SyntaxError('Invalid token: %r.' % tok)
		if len(stack) != 1:
			adj = 'many' if len(stack) > 1 else 'few'
			raise SyntaxError('Too %s operands to process.' % adj)
		return stack[0]


class RPNWithFunctions(RPN):
	'''Reverse Polish Notation interpreter with function support.
	
	Functions are defined as follow::
	
		:function-name :argument-count :istructions def
	
	Each token that is part of the function must be prefixed with
	the ':'.
	
	An example::
	
		:add-and-double :2 :+ :2 :* def 1 1 add-and-double
	
	This should return (1+1)*2->4
	'''
	
	def __init__(self, operators=None):
		super(RPNWithFunctions, self).__init__(operators)
		
		self._funcparts = []
		self._func_defined = {}
		
		self._token_types.insert(0,
			(self.is_funcpart_token, self.handle_funcpart_token))
		self._token_types.insert(0,
			(self.is_definition_token, self.handle_definition_token))
		self._token_types.insert(0,
			(self.is_funccall_token, self.handle_funccall_token))
		
	def is_funcpart_token(self, tok):
		'''Return True if *tok* is part of a function.'''
		
		return tok.startswith(':')
	
	def handle_funcpart_token(self, tok, stack):
		'''Handle a funcpart token.'''
		
		self._funcparts.append(tok)
	
	def is_funccall_token(self, tok):
		'''Return True if *tok* is a function call.'''
		
		return tok in self._func_defined
	
	def handle_funccall_token(self, tok, stack):
		'''Executes a function call.'''
		
		number_of_operands = self._func_defined[tok][1]
		if len(stack) < number_of_operands:
			raise SyntaxError('Too few arguments.')
		operands = stack[:number_of_operands]
		del stack[:number_of_operands]
		stack.insert(0, self._func_defined[tok][0](*operands))
	
	def is_definition_token(self, tok):
		'''Return True if *tok* is the definition token.'''
		
		return tok == 'def'
	
	def handle_definition_token(self, tok, stack):
		'''Handle a definition token.
		
		This method builds and saves the function
		whose token were collected in the _funcparts
		list.
		'''
		
		for i, t in enumerate(self._funcparts):
			if not t.startswith(':'):
				raise SyntaxError('Invalid token in function: %r.' % t)
			self._funcparts[i] = t[1:]
		
		name = self._funcparts.pop(0)
		if name in self._operators:
			raise ValueError('This operator is already defined.')
		elif name in self._func_defined:
			raise ValueError('This function is already defined.')
		
		number_of_operands = int(self._funcparts.pop(0))
		funcparts = self._funcparts
		self._funcparts = []
		
		if not funcparts:
			raise SyntaxError('Function cannot be empty.')
		
		result = []
		
		for token in funcparts:
			if self.is_input_token(token):
				result.append(self.evaluate_input(token))
			elif self.is_operator_token(token):
				result.append((token, self._operators[token]))
			elif self.is_funccall_token(token):
				result.append((token, self._func_defined[token]))
			else:
				raise SyntaxError('Invalid token in function: %r.' % token)
		
		def funccall(*operands):
			'''Calls the function on *operands* and returns the result.'''
			
			operands = list(operands)
			for r_tok in result:
				try:
					tok_name, (func, num_op) = r_tok
					ops = operands[:num_op]
					del operands[:num_op]
					if tok_name in self._operators:
						operands.insert(0, self.evaluate(tok_name, ops))
					else:
						res = self._func_defined[tok_name][0](*ops)
						operands.insert(0, res)
				except TypeError:
					operands.insert(0, r_tok)
					continue
			
			if len(operands) != 1:
				adj = 'many' if len(operands) > 1 else 'few'
				raise SyntaxError('Too %s arguments.' % adj)
			
			return operands[0]
		
		self._func_defined[name] = (funccall, number_of_operands)
	
	def execute(self, code, keep_functions=False):
		'''Executes RPN code with function support.'''
		
		self._funcparts = []
		if not keep_functions:
			self._func_defined = {}
		
		return super(RPNWithFunctions, self).execute(code)
 	
